﻿#include<iostream>

//常数阶
int Constant(int n) {
	int count = 0;
	int size = 1000;
	for (int i = 0; i < size; i++)
		count++;
	return count;
}
//线性阶
int Linear(int n) {
	int count = 0;
	for (int i = 0; i < n; i++)
		count++;
	return count;
}
//平方阶
int Quadratic(int n) {
	int count = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			count++;
		}
	}
	return count;
}
//指数阶
int Exponential(int n) {
	//count是当前分裂次数，base是当前轮的分裂数，total是当前轮的分裂总数
	int count = 0, base = 1, total = 1;
		//细胞每次1分2,2分4到最后2^(n-1)
	if (n == 1)
		return 1;
	while (count < n-1) {
		base *= 2;
		total += base;
		count++;
		std::cout << "base:" << base << ",total:" << total << ",count:" << count << std::endl;
	}
	return total;
}
//初始1个，第1轮1+2个，第2轮1+2+4个
int Exponential2(int n) {
	if (n == 1)
		return 1;
	return Exponential2(n - 1) + Exponential2(n - 1) + 1;
}
//对数阶
int Logarithmic(int n) {
	int count = 0;
	while (n > 1) {
		n = n / 2;
		count++;
	}
	return count;
}
int Logarithmic2(int n) {
	if (n <= 1)
		return 0;
	return Logarithmic2(n / 2) + 1;
}
//线性对数阶
int LinearLogRecur(int n) {
	if (n <= 1)
		return 1;
	int count = LinearLogRecur(n / 2) + LinearLogRecur(n / 2);
	for (int i = 0; i < n; i++)
		count++;
	return count;
}
//阶乘阶
int factorialRecur(int n) {
	if (n == 0)
		return 1;
	int count = 0;
	for (int i = 0; i < n; i++) {
		count += factorialRecur(n - 1);
	}
	return count;
}

int main() {
	//时间复杂度
	int n = 5;
	std::cout << "Exponential 5:" << Exponential(3) << std::endl;

	std::cout << "Exponential2 5:" << Exponential2(3) << std::endl;

	std::cin.get();
}